The subject of the invention is a method of binary multiplication of a number by a sum of two numbers and a digital system for implementation thereof. The invention is applicable in digital computers and computing systems and particularly in rapid specialized processors for digital computations as well as in other rapid digital facilities performing arithmetic operations.
In the known solutions of the digital multiplying systems, rapid execution of binary multiplication of a number by a sum of two numbers-summands is realized by a rapid addition of the two summands and then a rapid multiplication of the above mentioned number by a sum of the two summands. Considerable speed of summation may be obtained in digital computers by the application of parallel adding systems provided with additional, sometimes extremely complicated, systems reducing the add carry propagation time. However, more important is a reduction of the time of multiplication since it lasts considerably longer than the summation. Binary multiplication in digital computers is usually performed by adding a sequence of partial products, which are the multiples of multiplicand shifted with respect to one another, obtained in course of multiplication of multiplicand by the component parts of multiplier, these being represented in the binary multiplication systems by bits or groups of bits of multiplier. Very great speeds of binary multiplication are obtained by summing simultaneously, in a parallel way, many partial products each of which corresponds to a group of several binary positions of the multiplier. Most rapid of the known methods of simultaneous addition of many multi-bit partial products is the method presented in the following works: C. S. Wallace's work entitled "A suggestion for a fast multiplier", "The Institute of Electrical and Electronics Engineers Transactions of Electronic Computers", volume EC-13, pages 14-17, February 1964 and T. G. Hallin's and M. J. Flynn's work entitled "Pipelining of arithmetic functions", The Institute of Electrical and Electronics Engineers Transactions of Electronic Computers, volume EC-21, pages 880-886, August 1972. Implementation of this method in the digital systems is presented in the above mentioned works in an example of a system consisting of a large number of carry save adders arranged in a tree structure with one additional carry propagating adder on the output of the adder tree, the said adder provided with systems increasing to the greatest possible extent the speed of carry propagation. The total number of partial products supplied to the inputs of this adder tree and summed in the course of multiplication may be several times smaller than the number of bits of multiplier, provided the individual partial products are multiples of the multiplicand corresponding to several-bit groups of multiplier bits.
The alternate addition and multiplication being encountered relatively frequently in digital computations requires reservation of a definite time for add-carry propagation in the course of addition. This must be realized after completion of the add carry propagation finishing the preceding multiplication. When using the described very fast multiplying system the relative time consumption for the realization of addition can be relatively large. This is a considerable drawback of the heretofore known solutions of very fast systems performing the binary multiplication of a number by a sum of two numbers.
The aim of the present invention is the elimination of this drawback as well as the complete elimination of execution of effective addition of two numbers consisting of summands of one factor of binary multiplication.